class Array
  def extract_submatrix(row_range, col_range)
    self[row_range].transpose[col_range].transpose
  end
  def traverse
  	self.each_index do |i|
      self[i].each_index do |j| 
        yield i,j
      end
    end
  end
  
  def get_submatrix_by_index(index)
    self.extract_submatrix((index/3*3)..(index/3*3+2), (index%3*3)..(index%3*3+2))
  end
  
  def to_submatrix_index
  	y, x = self.at(0), self.at(1)
  	return (y/3).floor * 3 + (x/3).floor
  end
end

class SudokuSolver
  def initialize(board)
    @board = board
    @available_moves = Array.new(9) do
    	Array.new(9) { [1,2,3,4,5,6,7,8,9] }
	end
  end

  def valid_row?(row_num)
    valid?(@board[row_num])
  end

  def valid_column?(col_num)
    valid?(@board.transpose[col_num])
  end

  def valid?(array)
    array.reject{|x| x==0}.uniq! == nil
  end
  
  def get_most_constrained
    min_open = 10
    min_index = 0
    @board.each_index do |i|
      this_open = @board[i].length - @board[i].reject{|x| x==0}.length
      min_open, min_index = this_open, i.to_s + " r" if this_open < min_open 
    end
    #min_row = @board[min_index.split(" ")]
    
    @board.transpose.each_index do |i|
      this_open = @board.transpose[i].length - @board.transpose[i].reject{|x| x==0}.length
      min_open, min_index = this_open, i.to_s + " c" if this_open < min_open 
    end
    
    (0..8).each do |index|
      flat_subm = @board.get_submatrix_by_index(index).flatten
      this_open = flat_subm.length - flat_subm.reject{|x| x==0}.length
      min_open, min_index = this_open, index.to_s + " m" if this_open < min_open
    end
   
    return min_index
    
  end
  
  def get_available_numbers_from_constrained(most_constrained)
  	index, flag = most_constrained.split(" ")[0].to_i,most_constrained.split(" ")[1] 
    avail = [1,2,3,4,5,6,7,8,9] - @board[index] if flag == "r"
    avail = [1,2,3,4,5,6,7,8,9] - @board.transpose[index] if flag == "c"
    avail = [1,2,3,4,5,6,7,8,9] - @board.get_submatrix_by_index(index).flatten if flag == "m"
    return avail
  end

  def get_available_numbers(indices)
  	y,x = indices[0], indices[1]
  	# removing rows
  	@available_moves[y][x] = @available_moves[y][x] - @board[y].reject{|i| i==0}
  	# removing columns
  	@available_moves[y][x] = @available_moves[y][x] - @board.transpose[x].reject{|i| i==0}
  	# removing submatrix
  	@available_moves[y][x] = @available_moves[y][x] - @board.get_submatrix_by_index(indices.to_submatrix_index).flatten.reject{|i| i==0}
  end
  
  def get_first_empty_cell(most_constrained)
    index, flag = most_constrained.split(" ")[0].to_i,most_constrained.split(" ")[1]
    result = index, @board[index].index(0) if flag == "r"
    result = @board.transpose[index].index(0), index if flag == "c"
    if flag == "m"
    	# flatten submatrix, find first 0
    	i = @board.get_submatrix_by_index(index).flatten.index(0)
    	
    	# relative coordinate within this submatrix
    	y = (i/3).floor
    	x = i % 3
    	
    	# absolute coordinate
    	result = ((index/3).floor)*3 + y, index%3*3 + x
    end
    	
    return result
  end 
  
  def solve
	
  end
end